use crate::q::Solution;

#[allow(unused)]
impl Solution {
    pub fn xor_game(nums: Vec<i32>) -> bool {
        // 方法1
        // 假设有1个数字，那么alice必败，因为她拿了之后，没数字了。
        // 假设有2个数字，那么alice必胜，因为bob会到1个数字的情况
        // 假设有3个数字，那么alice必败，因为她拿了之后，bob就到2个数字的情况
        // 那么这样看来，只要n是偶数的情况下，Alice就会胜利
        // 等等，我们是不是漏了一个很重要的条件，那就是异或啊
        // 题目说道："换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。"
        // 也就是说，Alice必须保证本轮所有xor不为0，
        // 而这种轮流拿东西的游戏必然要考虑奇偶性，那么我们要考虑在Alice在面对偶数长度情况下是否能保持不败
        // 这样我们只需要让Alice处于偶数，就能胜利
        // 根据异或的特点，如果sum = 0，那么Alice自然就赢了，
        // 那么我们要看sum != 0的情况下，Alice要输的情况只有：
        // Alice无论拿哪个数字x，都使得剩下的n-1个数字的异或和为0。要证明这个事情我们需要反正法。
        // 唉，这道题变成数学题了。根据上面的描述，我们列出了等式：
        // S = nums[0] ^ nums[1] ^ .. ^ nums[n - 1]，S != 0，n 是偶数。
        // Si代表随便去掉一个数x之后的异或结果，那么有：Si ^ nums[i] = S，两边同时异或nums[i]得到：
        // Si = nums[i] ^ S，由于无论拿掉哪个数字都使得Si为0，而0 ^ x = x，那么就有：
        // S0 ^ S1 ^ .. S^n-1 = 0,把上式代入这个式子得到：
        // (nums[0] ^ S) ^ (nums[1] ^ S) ^ ... (nums[n-1] ^ S) = 0，异或满足交换律得到：
        // (S^..^S) ^ (nums[0] ^...^ nums[n-1]) = 0，那么S有n个，是偶数所以得到：
        // 0 ^ S = 0，得到 S = 0
        // 而之前假设S != 0，所以前后矛盾，那么意味着只要是偶数，Alice就必然有必胜法
        // 证明完成之后，这道题就简单了
        // AC 0ms 1.9mb
        let sum = nums.iter().fold(0, |acc, &x| acc ^ x);
        if sum == 0 { true } else { nums.len() % 2 == 0 }
    }
}